from typing import List
from collections import defaultdict
inf = 0x3f3f3f3f
class DvRouter : pass
class MyNet : pass
class DvRouter:
    def __init__(self, name:str, net:MyNet) -> None:
        self.name = name
        self.has_changed = True
        self.has_news = True
        self.net:MyNet = net
        self.neighbors:set[DvRouter] = set()
        self._tmp_table : dict[str,dict[str,int]] = defaultdict(lambda:defaultdict(lambda:inf))
        self.routing_table: dict[str,dict[str,int]] = defaultdict(lambda:defaultdict(lambda:inf))
        self.routing_table[name][name] = 0

    def addNeighbor(self,neighbor:DvRouter,dis:int):
        nei_name = neighbor.name
        self.routing_table[self.name][nei_name] = dis
        self.routing_table[nei_name]
        self.neighbors.add(neighbor)
    
    def boardcast(self):
        vector = self.routing_table[self.name]
        for neighbor in self.neighbors:
            neighbor.beBoardcast(self.name,vector)
    
    def beBoardcast(self,src_name: str, vector:dict[str,int]):
        self.has_news = True
        self.routing_table[src_name] = vector.copy()
    
    def compute(self):
        self.has_changed = False
        if not self.has_news: return
        old_vector:dict[str,int] = self.routing_table[self.name]
        new_vector:dict[str,int] = old_vector.copy()
        for neighbor_name, neighbor_vector in self.routing_table.items():
            if neighbor_name == self.name: continue
            for dest_name, dis in neighbor_vector.items():
                if dis >= inf: continue
                tmp_dis = old_vector[neighbor_name] + dis
                if tmp_dis >= new_vector[dest_name]: continue
                self.has_changed = True
                tmppp = new_vector[dest_name] if new_vector[dest_name] < inf else "inf"
                print(f"dis from {self.name} to {dest_name}, changes from {tmppp} to {tmp_dis}")
                new_vector[dest_name] = tmp_dis
        self.routing_table[self.name] = new_vector.copy()

    def __str__(self) -> str:
        all_nodes_name = list(self.net.all_notes_name)
        string = "|%-8s|" % ("Node: "+self.name)
        for name in all_nodes_name:
            string += " %-4s|" % (name)
        string += "\n"
        for neighbor_name, neighbor_vector in self.routing_table.items():
            string += "|%-8s|" % neighbor_name
            for name in all_nodes_name:
                dis = neighbor_vector[name] if neighbor_vector[name] < inf else ""
                string += " %-4s|" % str(dis)
            string += "\n"
        return string

class MyNet:
    def __init__(self,edges: List[tuple[str]]) -> None:
        self.is_running = True
        self.step = 0
        self.router_dict:dict[str,DvRouter] = {} # str:DvRouter
        for edge in edges:
            assert len(edge) == 3, "an edge's length should be 2."
            uname,vname,dis = edge
            u,v= self.getRouterByName(uname),self.getRouterByName(vname)
            assert isinstance(u,DvRouter)
            assert isinstance(v,DvRouter)
            u.addNeighbor(v,dis)
            v.addNeighbor(u,dis)
        print(self)


    @property
    def all_notes_name(self):
        return sorted(self.router_dict.keys())
    
    def boardcast(self) -> bool:
        has_changed = False
        for router in self.router_dict.values():
            if router.has_changed:
                has_changed = True
                router.boardcast()
        return has_changed

    def reCompute(self):
        for router in self.router_dict.values():
            router.compute()

    def __str__(self):
        return "\n".join(str(r) for r in self.router_dict.values())

    def update(self) -> bool:
        self.step += 1
        print(f"step:{self.step}")
        if not self.boardcast():
            return False
        self.reCompute()
        print()
        print(str(self))
        return True

    def start(self):
        fl = True
        while fl:
            fl = self.update()

    def stop(self):
        self.is_running = False

    def nameToRouter(self,name:str)->DvRouter|None:
        return  self.router_dict.get(name,None)
    # if not exits, create a new node and return it 
    def getRouterByName(self,name:str)->DvRouter:
        tmp_node = self.nameToRouter(name)
        if tmp_node is not None: return tmp_node
        self.router_dict[name] = DvRouter(name,self)
        return self.router_dict[name]

import sys
if __name__ == "__main__": 
    with open("output.txt", "w") as f:
        original_stdout = sys.stdout
        sys.stdout = f
        edges = [
            ("u","v",1),
            ("u","y",2),
            ("x","y",3),
            ("x","v",3),
            ("z","v",6),
            ("x","z",2)
        ]
        mynet = MyNet(edges)
        mynet.start()
        sys.stdout = original_stdout